package 题目集.动态规划.背包问题;

import java.util.Arrays;
import java.util.List;
import java.util.TreeMap;

import org.junit.Test;

/**
 * https://leetcode.cn/problems/last-stone-weight-ii/description/ 这题和任意石子合并类似。
 * 这题和任意石子合并有点区别，任意石子合并有合并的代价。 这题没有合并的代价。 这题的最优解是让两个子集的和尽可能的接近。
 * 相当于是有N个数可选，从中能选出的小于等于sum/2（背包容量）的结果。
 * dp[i][j]定义为：总容量为j时，有i个物品可选的最大值。
 */
public class ch04_最后一块石头的重量 {
// 	//错误思路
//	public int lastStoneWeightII(int[] stones) {
//		src = stones;
//		int sum = Arrays.stream(stones).sum();
//		int su = (sum - 1) / 2 + 1; // 向上取整
//		dp = new int[stones.length + 1][su + 1];
//		for (int[] ints : dp) {
//			Arrays.fill(ints, -1);
//		}
//		int um = dfs(stones.length, su);
//		return Math.abs(um - (sum - um));
//	}
//	int[] src;
//	int[][] dp;
//	public int dfs(int i, int sum) {
//		if (i == 0) {
//			return 0;
//		}
//		if (dp[i][sum] != -1) {
//			return dp[i][sum];
//		}
//		int nochose = dfs(i - 1, sum);
//		int chose = 0;
//
//		if (sum >= src[i - 1]) {
//			chose = dfs(i - 1, sum - src[i - 1]) + src[i - 1];
//		}
//		dp[i][sum] = Math.max(chose, nochose);
//		return dp[i][sum];
//	}

	public int lastStoneWeightII(int[] stones) {
		src = stones;
		int sum = Arrays.stream(stones).sum();
		int su = (sum - 1) / 2 + 1;
		int um = dp(su);
		return Math.abs(um - (sum - um));
	}

	int[] src;

	public int dp(int sum) {
		int[] dp = new int[sum + 1];
		for (int i = 1; i <= src.length; i++) {
			for (int j = sum; j > 0; j--) {	//这里压缩成一维需要反过来遍历，会污染上一层的数据
				if (j >= src[i - 1]) {
					dp[j]= Math.max(dp[j], dp[j - src[i - 1]] + src[i - 1]);
				}
			}
		}
		return dp[sum];
	}
	public int dp2(int sum) {
		int[][] dp = new int[src.length + 1][sum + 1];
		for (int i = 1; i <= src.length; i++) {
			for (int j = 1; j <= sum; j++) {
				int nochose = dp[i - 1][j];
				int chose = 0;
				if (j >= src[i - 1]) {
					chose = dp[i - 1][j - src[i - 1]] + src[i - 1];
				}
				dp[i][j] = Math.max(nochose, chose);
			}
		}
		for (int[] ints : dp) {
			System.out.println(Arrays.toString(ints));
		}
		return dp[src.length][sum];
	}
	@Test
	public void test() {
		int[] arr = { 31,26,33,21,40 };
		int res = lastStoneWeightII(arr);
		System.out.println(res);
	}
}
